package com.wang.utils.sort;

import java.util.Arrays;

/**
 * @author 86173
 * @date 2021/7/30 18:41
 */

/**
 * 冒泡排序的改进
 */
public class QuickSort {

	public static void main(String[] args) throws Exception {
		int[] arr = {1,9,8,2,4};
		QuickSort qs = new QuickSort();
		int[] sort = qs.sort(arr);
		System.out.println(Arrays.toString(sort));
	}

	public int[] sort(int[] sourceArray) throws Exception {
		// 对 arr 进行拷贝，不改变参数内容
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		return quickSort(arr, 0, arr.length - 1);
	}

	//设定两个索引值
	private int[] quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int partitionIndex = partition(arr, left, right);
			//左边 找小于基准位置的值
			quickSort(arr, left, partitionIndex - 1);
			//右边 找大于基准位置的值
			quickSort(arr, partitionIndex + 1, right);


		}
		return arr;
	}

	private int partition(int[] arr, int left, int right) {
		// 设定基准值（pivot）
		int pivot = left;
		int index = pivot + 1;
		//左边
		for (int i = index; i <= right; i++) {
			if (arr[i] < arr[pivot]) {
				swap(arr, i, index);
				index++;
			}
		}
		//找右边
		swap(arr, pivot, index - 1);
		return index - 1;
	}

	//数据进行交换，交换的基准位两边的数据交换，得到一个左边小于基准值，右边大于基准值的结果，不断的进行这样的操作
	private void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
